20220307-TIL

오늘은 친구가 오토바이 옮기는 것 좀 도와달라길래 도와주고 왔다. (만난 김에 같이 게임도 함)

오늘 알고리즘 문제는 플로이드 알고리즘을 제대로 이해해야 풀 수 있는 문제였다. (못 품 ㅜㅠ)

• 밤편지 문제는 각 중간 지점에 대한 최단 경로를 동적계획법을 이용해 구하는 식으로 풀었다.
• 처음에는 최단 거리를 구한 다음에 완전 탐색과 백트래킹을 활용하는 방법밖에 안 떠올랐다..
• 어떤 수 t보다 작은 번호의 집만 거쳐 갈 때의 최단 경로를 구하는 식의 풀이도 떠오르긴 했다.
  (분명 좋은 아이디어였는데 O(n^4) 이라 포기 -> 동적계획법을 적용하면 바로 해결될 문제였음;)